1
2
3
4 package joeq.Allocator;
5
6 import java.util.Iterator;
7 import java.util.List;
8 import java.util.SortedMap;
9 import java.util.TreeMap;
10 import joeq.Class.PrimordialClassLoader;
11 import joeq.Class.jq_BytecodeMap;
12 import joeq.Class.jq_Class;
13 import joeq.Class.jq_CompiledCode;
14 import joeq.Class.jq_InstanceField;
15 import joeq.Class.jq_Method;
16 import joeq.Class.jq_StaticField;
17 import joeq.Class.jq_TryCatch;
18 import joeq.Memory.Address;
19 import joeq.Memory.CodeAddress;
20 import joeq.Runtime.ExceptionDeliverer;
21
22 /***
23 * This class provides the abstract interface for code allocators. A code
24 * allocator handles the allocation and management of code buffers.
25 *
26 * It also provides static methods for keeping track of the compiled methods and
27 * their address ranges.
28 *
29 * It also includes an inner class that provides the interface for code buffers.
30 *
31 * @author John Whaley <jwhaley@alum.mit.edu>
32 * @version $Id: CodeAllocator.java 1941 2004-09-30 03:37:06Z joewhaley $
33 */
34 public abstract class CodeAllocator {
35
36 /*** Trace flag. */
37 public static
38
39 /***
40 * Initialize this code allocator. This method is always called before the
41 * code allocator is actually used.
42 */
43 public abstract void init();
44
45 /***
46 * Allocate a code buffer of the given estimated size, such that the given
47 * offset will have the given alignment.
48 * It is legal for code to exceed the estimated size, but the cost may be
49 * high (i.e. it may require recopying of the buffer.)
50 *
51 * @param estimatedSize estimated size, in bytes, of desired code buffer
52 * @param offset desired offset to align to
53 * @param alignment desired alignment, or 0 if don't care
54 * @return the new code buffer
55 */
56 public abstract x86CodeBuffer getCodeBuffer(int estimatedSize,
57 int offset,
58 int alignment);
59
60 /***
61 * Patch the given address to refer to the other given address, in
62 * absolute terms. This is used to patch heap address references in the
63 * code, and code references in the heap.
64 *
65 * @param addr1 address to patch
66 * @param addr2 address to patch to
67 */
68 public abstract void patchAbsolute(Address addr1,
69 Address addr2);
70
71 /***
72 * Patch the given code address to refer to the given code address, in
73 * relative terms. This is used to patch branch targets in the code.
74 *
75 * @param code code address to patch
76 * @param target code address to patch to
77 */
78 public abstract void patchRelativeOffset(CodeAddress code,
79 CodeAddress target);
80
81 /***
82 * This class provides the interface for x86 code buffers.
83 * These code buffers are used to store generated x86 code.
84 * After the code is generated, use the allocateCodeBlock method to obtain
85 * a jq_CompiledCode object.
86 */
87 public abstract static class x86CodeBuffer {
88
89 /***
90 * Returns the current offset in this code buffer.
91 * @return current offset
92 */
93 public abstract int getCurrentOffset();
94
95 /***
96 * Returns the current address in this code buffer.
97 * @return current address
98 */
99 public abstract CodeAddress getStartAddress();
100
101 /***
102 * Returns the current address in this code buffer.
103 * @return current address
104 */
105 public abstract CodeAddress getCurrentAddress();
106
107 /***
108 * Sets the current address as the entrypoint to this code buffer.
109 */
110 public abstract void setEntrypoint();
111
112 /***
113 * Adds one byte to the end of this code buffer. Offset/address
114 * increase by 1.
115 * @param i the byte to add
116 */
117 public abstract void add1(byte i);
118
119 /***
120 * Adds two bytes (little-endian) to the end of this code buffer.
121 * Offset/address increase by 2.
122 * @param i the little-endian value to add
123 */
124 public abstract void add2_endian(int i);
125
126 /***
127 * Adds two bytes (big-endian) to the end of this code buffer.
128 * Offset/address increase by 2.
129 * @param i the big-endian value to add
130 */
131 public abstract void add2(int i);
132
133 /***
134 * Adds three bytes (big-endian) to the end of this code buffer.
135 * Offset/address increase by 3.
136 * @param i the big-endian value to add
137 */
138 public abstract void add3(int i);
139
140 /***
141 * Adds four bytes (little-endian) to the end of this code buffer.
142 * Offset/address increase by 4.
143 * @param i the little-endian value to add
144 */
145 public abstract void add4_endian(int i);
146
147 /***
148 * Gets the byte at the given offset in this code buffer.
149 *
150 * @param k offset of byte to return
151 * @return byte at given offset
152 */
153 public abstract byte get1(int k);
154
155 /***
156 * Gets the (little-endian) 4 bytes at the given offset in this
157 * code buffer.
158 *
159 * @param k offset of little-endian 4 bytes to return
160 * @return little-endian 4 bytes at given offset
161 */
162 public abstract int get4_endian(int k);
163
164 /***
165 * Sets the byte at the given offset to the given value.
166 * @param k offset of byte to set
167 * @param instr value to set it to
168 */
169 public abstract void put1(int k, byte instr);
170
171 /***
172 * Sets the 4 bytes at the given offset to the given (little-endian)
173 * value.
174 * @param k offset of 4 bytes to set
175 * @param instr little-endian value to set it to
176 */
177 public abstract void put4_endian(int k, int instr);
178
179 public abstract void skip(int nbytes);
180
181 /***
182 * Uses the code in this buffer, along with the arguments, to create
183 * a jq_CompiledCode object. Call this method after you are done
184 * generating code, and actually want to use it.
185 *
186 * @param m Java method of this code block, or null if none
187 * @param ex exception handler table, or null if none
188 * @param bcm bytecode map, or null if none
189 * @param x exception deliverer to use for this code, or null if none
190 * @param stackframesize size of stack frame in bytes
191 * @param codeRelocs list of code relocations for this code buffer, or
192 * null if none
193 * @param dataRelocs list of data relocations for this code buffer, or
194 * null if none
195 * @return a new jq_CompiledCode object for the code
196 */
197 public abstract jq_CompiledCode allocateCodeBlock(jq_Method m,
198 jq_TryCatch[] ex,
199 jq_BytecodeMap bcm,
200 ExceptionDeliverer x,
201 int stackframesize,
202 List codeRelocs,
203 List dataRelocs);
204 }
205
206 /*** Map of compiled methods, sorted by address. */
207 public static final SortedMap compiledMethods;
208
209 /***
210 * Address range of compiled code. Code outside of this range cannot be
211 * generated by us.
212 */
213 private static CodeAddress lowAddress, highAddress;
214 static {
215 compiledMethods = new TreeMap();
216 }
217
218 public static void initializeCompiledMethodMap() {
219 lowAddress = (CodeAddress) CodeAddress.getNull().offset(0x7FFFFFFF);
220 highAddress = CodeAddress.getNull();
221 jq_CompiledCode cc = new jq_CompiledCode(null, highAddress, 0, highAddress,
222 null, null, null, 0, null, null);
223 compiledMethods.put(cc, cc);
224 }
225
226 /***
227 * Register the given compiled code, so lookups by address will return
228 * this code.
229 *
230 * @param cc compiled code to register
231 */
232 public static void registerCode(jq_CompiledCode cc) {
233 if (TRACE) System.out.println("Registering code: " + cc);
234 if (lowAddress == null || cc.getStart().difference(lowAddress) < 0)
235 lowAddress = cc.getStart();
236 if (highAddress == null || highAddress.difference(cc.getStart().offset(cc.getLength())) < 0)
237 highAddress = (CodeAddress)cc.getStart().offset(cc.getLength());
238 compiledMethods.put(cc, cc);
239 }
240
241 /***
242 * Return the compiled code which contains the given code address.
243 * Returns null if there is no registered code that contains the
244 * given address.
245 *
246 * @param ip code address to check
247 * @return compiled code containing given address, or null
248 */
249 public static jq_CompiledCode getCodeContaining(CodeAddress ip) {
250 InstructionPointer iptr = new InstructionPointer(ip);
251 return (jq_CompiledCode) compiledMethods.get(iptr);
252 }
253
254 /***
255 * Returns the lowest address of any registered code.
256 * @return lowest address of any registered code.
257 */
258 public static CodeAddress getLowAddress() { return lowAddress; }
259 /***
260 * Returns the highest address of any registered code.
261 * @return highest address of any registered code.
262 */
263 public static CodeAddress getHighAddress() { return highAddress; }
264
265 /***
266 * Returns an iterator of the registered jq_CompiledCode objects, in
267 * address order.
268 * @return iterator of jq_CompiledCode objects
269 */
270 public static Iterator
271 Iterator i = compiledMethods.keySet().iterator();
272 i.next();
273 return i;
274 }
275
276 /***
277 * Returns the number of registered jq_CompiledCode objects.
278 * @return number of registered jq_CompiledCode objects
279 */
280 public static int getNumberOfCompiledMethods() {
281 return compiledMethods.keySet().size() - 1;
282 }
283
284 /***
285 * An object of this class represents a code address.
286 * It can be compared with a jq_CompiledCode object with compareTo and
287 * equals. They are equal if the InstructionPointer points within the
288 * range of the compiled code; the InstructionPointer is less if it is
289 * before the start address of the compiled code; the InstructionPointer
290 * is less if it is after the end address of the compiled code.
291 */
292 public static class InstructionPointer implements Comparable {
293
294 /*** The (actual) address. */
295 private final CodeAddress ip;
296
297 /***
298 * Create a new instruction pointer.
299 * @param ip instruction pointer value
300 */
301 public InstructionPointer(CodeAddress ip) { this.ip = ip; }
302
303 /***
304 * Extract the address of this instruction pointer.
305 * @return address of this instruction pointer
306 */
307 public CodeAddress getIP() { return ip; }
308
309 /***
310 * Compare this instruction pointer to a compiled code object.
311 * @param that compiled code to compare against
312 * @return -1 if this ip comes before the given code, 0 if it is
313 * inside the given code, 1 if it is after the given code
314 */
315 public int compareTo(jq_CompiledCode that) {
316 CodeAddress ip = this.getIP();
317 CodeAddress start = that.getStart();
318 if (start.difference(ip) >= 0) return -1;
319 if (start.offset(that.getLength()).difference(ip) < 0) return 1;
320 return 0;
321 }
322
323 /***
324 * Compare this instruction pointer to another instruction pointer.
325 * @param that instruction pointer to compare against
326 * @return -1 if this ip is before the given ip, 0 if it is equal
327 * to the given ip, 1 if it is after the given ip
328 */
329 public int compareTo(InstructionPointer that) {
330 if (this.ip.difference(that.ip) < 0) return -1;
331 if (this.ip.difference(that.ip) > 0) return 1;
332 return 0;
333 }
334
335 /***
336 * Compares this instruction pointer to the given object
337 * (InstructionPointer or jq_CompiledCode)
338 * @param that object to compare to
339 * @return -1 if this is less than, 0 if this is equal, 1 if this
340 * is greater than
341 */
342 public int compareTo(java.lang.Object that) {
343 if (that instanceof jq_CompiledCode)
344 return compareTo((jq_CompiledCode) that);
345 else
346 return compareTo((InstructionPointer) that);
347 }
348
349 /***
350 * Returns true if this instruction pointer refers to a location
351 * within the given compiled code, false otherwise.
352 * @param that compiled code to compare to
353 * @return true if the instruction pointer is within, false otherwise
354 */
355 public boolean equals(jq_CompiledCode that) {
356 CodeAddress ip = this.getIP();
357 CodeAddress start = that.getStart();
358 if (ip.difference(start) < 0) return false;
359 if (ip.difference(start.offset(that.getLength())) > 0)
360 return false;
361 return true;
362 }
363
364 /***
365 * Returns true if this instruction pointer refers to the same location
366 * as the given instruction pointer, false otherwise.
367 * @param that instruction pointer to compare to
368 * @return true if the instruction pointers are equal, false otherwise
369 */
370 public boolean equals(InstructionPointer that) {
371 return this.ip.difference(that.ip) == 0;
372 }
373
374 /***
375 * Compares this instruction pointer with the given object
376 * (InstructionPointer or jq_CompiledCode).
377 * @param that object to compare with
378 * @return true if these objects are equal, false otherwise
379 */
380 public boolean equals(Object that) {
381 if (that instanceof jq_CompiledCode)
382 return equals((jq_CompiledCode) that);
383 else
384 return equals((InstructionPointer) that);
385 }
386
387 /***
388 * Returns the hash code of this instruction pointer.
389 * This is a really bad implementation (just returns 0), and
390 * should not be counted on.
391 * @return hash code
392 */
393 public int hashCode() { return 0; }
394
395 public static final jq_InstanceField _ip;
396 static {
397 jq_Class k = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType("Ljoeq/Allocator/CodeAllocator$InstructionPointer;");
398 _ip = k.getOrCreateInstanceField("ip", "I");
399 }
400 }
401
402 public static final jq_Class _class;
403 public static final jq_StaticField _lowAddress;
404 public static final jq_StaticField _highAddress;
405 public static final jq_StaticField _compiledMethods;
406 static {
407 _class = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType("Ljoeq/Allocator/CodeAllocator;");
408 _lowAddress = _class.getOrCreateStaticField("lowAddress", "Ljoeq/Memory/CodeAddress;");
409 _highAddress = _class.getOrCreateStaticField("highAddress", "Ljoeq/Memory/CodeAddress;");
410 _compiledMethods = _class.getOrCreateStaticField("compiledMethods", "Ljava/util/SortedMap;");
411 }
412 }